Talk:Second-order arithmetic
(This question looks a bit silly) Why it's called "second"-order arithmetic? Why "second"? Are there any other n-th-order arithmetic? {hyp/^,cos} (talk) 07:36, July 3, 2015 (UTC) : Basically, we have first-order arithmetic, which is the one which speaks only about natural numbers. Step higher is second-order arithmetic, which speaks about natural numbers and sets of these. Going even higher, we would have third-, fourth-, etc. order arithmetic, speaking respectively about families of sets, families of families of sets etc. : There are also axiom systems for these, but these are very rarely considered. LittlePeng9 (talk) 08:06, July 3, 2015 (UTC) : The language of first-order arithmetic is described on the page about Peano arithmetic. PA is an example of a theory of first-order arithmetic. : There is some naming asymmetry here, as the most popular axiomatized second-order arithmetic is called "second-order arithmetic" and the most popular axiomatized first-order arithmetic is called "Peano arithmetic." You could use "first-order arithmetic" to refer to PA, but that would most likely cause confusion. -- ve 08:56, July 3, 2015 (UTC) Question: What's \(\Pi_1^1\), \(\Sigma_1^0\) and \(\Delta_1^0\)? And what's \(\Pi_n^m\), \(\Sigma_n^m\) and \(\Delta_n^m\)? Another question: what's \(\Pi_1^1-CA_0+BI\)? {hyp/^,cos} (talk) 02:35, July 4, 2015 (UTC) :See and . These links are in the article. -- ve 04:44, July 4, 2015 (UTC) :Linked pages don't really explain other questions, so let me do this here. \(\Pi_n^m\), \(\Sigma_n^m\) and \(\Delta_n^m\) are natural extensions of \(\Pi_n^1\), \(\Sigma_n^1\) and \(\Delta_n^1\) to \(m-1\)-th order arithmetic. If it's of your interest I can provide a full definition of these. :\(BI\) denotes bar induction, which is slightly technical extension stating that for any well-order coded by an arithmetical formula we can do transfinite induction to prove any formula. LittlePeng9 (talk) 07:21, July 4, 2015 (UTC) :If I get it right, \(\Pi_0^0=\Sigma_0^0\) don't use any \(\forall\)'s or \(\exists\)'s. \(\Pi_{n+1}^m\) add some \(\forall\)'s on \(\Sigma_n^m\), and \(\Sigma_{n+1}^m\) add some \(\exists\)'s on \(\Pi_n^m\). And \(\Pi_0^{m+1}=\Sigma_0^{m+1}\) contain all the \(\Pi_n^m\) and \(\Sigma_n^m\) for all n. Finally \(\Delta_n^m\) is something both \(\Pi_n^m\) and \(\Sigma_n^m\). {hyp/^,cos} (talk) 11:32, July 4, 2015 (UTC) ::Almost - \(\Pi_0^0=\Sigma_0^0\) actually allows use of quantifiers, but they have to be bounded, meaning that they have to be of form \(\exists a1)\land\forall k2+PD is stronger than ZFC or n-th-order arithmetic for n>2 - language of second-order arithemetic is not expressive enough to make claims about arbitrary sets of reals (while other two systems are), let alone prove them. Noteworthy, it's also not the case that ZFC or n-th-order arithmetic are stronger than Z2+PD - they cannot prove PD, while Z2+PD has PD as axiom schema. : Of course, there are different possible notions of "stronger" one could consider, a natural one being "has larger PTO". Now I can't say that I know the answer in this case, but my intuition tells me that Z2+PD has smaller PTO than n-th-order arithmetic and ZFC. LittlePeng9 (talk) 06:48, July 6, 2015 (UTC) :I have found the answer on Wikipedia, see this article. Basically it says that, when talking about statements in language of Z2, then Z2+PD proves precisely the statements which can be proven in ZFC+for every n "there exist n Woodin cardinals". This actually implies that PTO of Z2+PD and ZFC+for every n "there exist n Woodin cardinals" are equal (and far larger than PTO of ZFC). So in this sense yes, Z2+PD is stronger than ZFC. LittlePeng9 (talk) 08:02, July 6, 2015 (UTC) WKL0 vs. RCA0 WKL0 is stronger than RCA0 since there's something WKL0 can proof but RCA0 cannot. However, it shows that both WKL0 and RCA0 have proof-theoretic ordinal \(\omega^\omega\) here . There must be something wrong! {hyp/^,cos} (talk) 00:27, July 8, 2015 (UTC) :There is nothing wrong. An interesting thing about RCA0 and WKL0 is that the latter is conservative over the former for first-order formulas, which means that RCA0 and WKL0 prove the same formulas not involving sets. This in particular makes their PTOs equal. :The point is, even though one theory can prove something that other can't, it need not be the case that these new theorems are statements which could possibly affect the PTO. LittlePeng9 (talk) 05:34, July 8, 2015 (UTC) :There are two misconceptions here: 1) all theories fall under a linear scale of "strength," and 2) "stronger" theories lead to ordinals with higher PTOs. Both are false. Theories are not like numbers, and they do not conform to a single order. There are many relations between theories, but "stronger" is not one that makes sense in general. -- ve 15:09, July 11, 2015 (UTC) ::The Big Five are an artificial "constellation" in the vast sky of theories. They happen to fall in a nice line, such that Pi11-CA0 properly extends ATR0 properly extends ACA0 properly extends WKL0 properly extends RCA0. I can easily pick theories that do not respect this order, such as RCA0 + the negation of the weak König's lemma. -- ve 15:31, July 11, 2015 (UTC) Intermediate value theorem? How can second-order arithmetic talk about functions on real numbers? There are \(\beth_2\) functions on real numbers, which can't be "encoded" into sets of natural numbers. {hyp/^,cos} (talk) 06:01, October 28, 2018 (UTC) : Arithmetic partially presents real functions. but does not fully deal with them. One way is to endode a real number into a sequence of natural numbers. Depending on how you encode it, you obtain a subset of real numbers which can be dealt with in arithmetic. Roughly speaking, real numbers corresponding to computable sequences can be handled. Since computable sequences can be encoded into natural numbers again, the notion of the computability of a real valued function again makes sense in arithmetic. For example, you can state intermediate value theorem for such "computable" real functions and their "computable" values. : p-adic 08:32, October 28, 2018 (UTC) How "choice" are \(\Sigma_n^m\)-AC? Are they weaker than the Axiom of Choice? If so, how strong are they compared with weaker forms of AC? Do they imply, for instance, the Banach-Tarski theorem? {hyp/^,cos} (talk) 02:23, November 12, 2018 (UTC) : It depends on how you state AC in second order arithmetic, because it is not allowed to quantify "a sequence of non-empty sets of natural numbers". If you encode "a sequence of non-empty sets of natural numbers" into "a \(2\)-ary \(\Sigma_n^m\)-formula \(\varphi(n,m)\) with \(\forall n, \exists m, \varphi(n,m)\)", then the resulting AC is just the same as \(\Sigma_n^m\)-AC. I am sorry but I do not know abot Banach-Tarski. : p-adic 07:27, November 13, 2018 (UTC) \(\Delta^m_n\) formulas How can a formula be \(\Delta^m_n\) for \(n>0\), i.e. both \(\Sigma^m_n\) and \(\Pi^m_n\)? The only probability, I think, is that the formula is either \(\Sigma^m_{n-1}\) or \(\Pi^m_{n-1}\), i.e. it has only at most n-1 alternative quantifier blocks. {hyp/^,cos} (talk) 15:11, September 29, 2019 (UTC) : The hierarchy is not determined by the shape of the formula itself, but is determined by its logical equivalence class. Therefore it can be represented by a formula in each hierarchy. : p-adic 21:56, September 29, 2019 (UTC)